// 2070. 每一个查询的最大美丽值
// AC: https://leetcode.cn/problems/most-beautiful-item-for-each-query/submissions/610861231/

class Solution {
public:
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        sort(items.begin(),items.end());
        int m=items.size();
        for(int i=1;i<m;++i){
            items[i][1]=max(items[i-1][1],items[i][1]);
        }
        int n=queries.size();
        for(int i=0;i<n;++i){
            int l=0,r=m;
            while(l<r){
                int mid=l+(r-l)/2;
                if(items[mid][0]>queries[i])
                    r=mid;
                else
                    l=mid+1;
            }
            if(l==0)
                queries[i]=0;
            else
                queries[i]=items[l-1][1];
        }
        return queries;
    }
};